import java.util.Comparator;
import java.util.PriorityQueue;
class IntCmp implements Comparator<Integer> {
    public int compare(Integer o1,Integer o2){
        return o2.compareTo(o1);
    }
}
public class test {

    //topK的简单解法
    public static int[] smallestK(int[] arr,int k){
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for(int j=0;j<k;j++){
            int val=minHeap.poll();
            tmp[j]=val;
        }
        return tmp;
    }

    public static int[] smallestK2(int[] arr,int k){
        int[] tmp=new int[k];
        if (k==0){
            return tmp;
        }
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new IntCmp());
        //将前k个元素放入堆中
        for(int i=0;i<k;i++){
            maxHeap.offer(arr[i]);
        }
        //遍历剩下的n-k个元素
        for (int i = k; i < arr.length; i++) {
            if(arr[i]<maxHeap.peek()){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            int val=maxHeap.poll();
            tmp[i]=val;
        }
        return tmp;
    }

    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        TestHeap testHeap = new TestHeap();
        testHeap.init(array);
        testHeap.createHeap();
        testHeap.heapSort();
    }
        public static void main2(String[] args) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(12);//默认创建的是一个小根堆
        priorityQueue.offer(5);
        priorityQueue.offer(57);

        System.out.println(priorityQueue.poll());//5
        System.out.println(priorityQueue.poll());//12
    }
    public static void main1(String[] args) {
        int[] array={27,15,19,18,28,34,65,49,25,37 };
        TestHeap testHeap=new TestHeap();
        testHeap.init(array);
        testHeap.createHeap();
//        testHeap.offer(80);
        testHeap.poll();
    }
}
